Esercizio Formalizzare in \(\mathbb{N}\) la seguente frase
Per ogni \(n > 1\) c’è un primo compreso tra \(n^2\) e \((n + 1)^2\).
usando soltanto i simboli \(\cdot\), \(<\) e \(1\) (interpretati nella maniera usuale) e un simbolo di predicato unario \(P\) per “essere primo”.
\[\begin{gathered} \forall{ x} \bigl( x > 1 \rightarrow \exists y \exists z ( x < y \mathbin{ \wedge } \neg \exists w ( x < w < y ) \bigr. \\ \bigl. {} \mathbin{ \wedge } x\cdot x < z < y\cdot y \mathbin{ \wedge } P ( z ) ) \bigr )\end{gathered}\]
Alternativa:
\[\begin{gathered} \forall x \forall{y} \bigl( x >1 \mathbin{ \wedge } x < y \mathbin{ \wedge } \neg \exists w ( x < w < y ) \bigr. \\ \bigl. {} \to \exists z (x \cdot x < z < y \cdot y \mathbin{ \wedge } P(z)) \bigr )\end{gathered}\]
Esercizio Formalizzare in \(\mathbb{N}\) la seguente frase:
Per ogni numero \(k\) ci sono numeri primi \(p\) arbitrariamente grandi tali che \(p + k\) è primo e non c’è nessun primo compreso tra \(p\) e \(p + k\).
utilizzando il linguaggio contenente i simboli \(+\), \(<\) e il predicato unario \(P\) per “essere un numero primo”.
\[\forall x \forall y \exists{ z} \bigl( y < z \wedge P ( z ) \wedge P ( z + x ) \wedge \neg \exists w ( z < w < z + x \wedge P ( w ) ) \bigr )\]
Esercizio Formalizzare la frase
Tutti i nipoti amano i propri nonni.
considerando come universo del discorso l’insieme di tutte le persone ed utilizzando il linguaggio del prim’ordine formato due simboli di relazione binari \(G\) e \(A\) interpretati come segue:
\(G ( x , y )\) se e solo se \(x\) è genitore di \(y\),
\(A ( x , y )\) se e solo se \(x\) ama \(y\).
\[\forall x \forall{ y} \bigl ( \exists z ( G ( z , x ) \wedge G ( y , z )) \to A ( x , y ) \bigr )\]
Alternativa equivalente:
\[\forall x \forall y \forall{ z} \bigl ( G ( y , x ) \wedge G ( z , y ) \to A ( x , z ) \bigr )\]
Esercizio Formalizzare nel linguaggio \(L\) che ha un simbolo di relazione unario \(P\) e un simbolo di funzione unario \(f\) la seguente frase
Se ci sono almeno due elementi che soddisfano la proprietà \(P\), allora la funzione \(f\) è suriettiva.
(Come universo del discorso si può prendere il dominio di qualunque \(L\)-struttura: per la sua forma, la frase è in questo caso indipendente dalla struttura scelta.)
\[\exists x \exists y ( P ( x ) \wedge P ( y ) \wedge \neg ( x = y ) ) \to \forall y \exists x ( f ( x ) = y )\]
Esercizio Formalizzare le frasi
Chi è amico di qualcuno che ama il cinema, ama il cinema.
Chi ama il teatro, è amico di qualcuno che ama il teatro.
Barbara è amica di Donatella e ama il teatro, ma non il cinema.
considerando come universo del discorso l’insieme di tutte le persone e utilizzando il linguaggio del prim’ordine formato da:
un simbolo di relazione unario \(C\): \(C(x) \leadsto\) “\(x\) ama il cinema”;
un simbolo di relazione unario \(T\): \(T(x) \leadsto\) “\(x\) ama il teatro”;
un simbolo di relazione binario \(A\): \(A ( x , y ) \leadsto\) “\(x\) è amico di \(y\)”;
due simboli di costante \(b\) e \(c\) interpretati come Barbara e Donatella.
\(\forall{ x} \bigl ( \exists y (A(x,y) \wedge C(y) ) \to C(x) \bigr)\)
\(\forall{ x} \bigl ( T(x) \to \exists y (A(x,y) \wedge T(y)) \bigr )\)
\(A(b,d) \wedge T(b) \wedge \neg C(b)\)
Esercizio Formalizzare in \(\mathbb{N}\) la seguente frase
Ogni numero dispari è somma di tre numeri primi.
usando soltanto i simboli di addizione \(+\) e un simbolo di predicato unario \(P\) per “essere primo”.
\[\begin{gathered} \forall{ x} \bigl( \neg \exists y \left ( y + y = x \right ) \to \exists z_{1} \exists z_{2} \exists z_{3} \bigr. \\ \bigl. \left ( P( z_{1} ) \wedge P ( z_{2} ) \wedge P ( z_{3} ) \wedge x = z_{1} + z_{2} + z_{3} \right ) \bigr )\end{gathered}\]
Esercizio Formalizzare in \(\mathbb{N}\) la seguente frase
Ogni numero dispari sufficientemente grande è somma di tre primi.
usando solo l’ordinamento \(<\), la somma \(+\) e il predicato unario \(P\) per “essere primo”.
\[\begin{gathered} \exists x \forall y \bigl ( x < y \mathbin{ \wedge } \neg \exists z ( z + z = y) \to \exists w_{1} \exists w_{2} \exists w_{3} \\ ( P ( w_{1} ) \mathbin{ \wedge } P( w_{2}) \mathbin{ \wedge } P ( w_{3} ) \mathbin{ \wedge } y = w_{1} + w_{2} + w_{3} ) \bigr )\end{gathered}\]
Esercizio Formalizzare la frase
Se tutti i tedeschi sono biondi e Andrea non è biondo, allora Andrea non è tedesco.
considerando come universo del discorso l’insieme di tutte le persone e utilizzando un linguaggio del prim’ordine con due simboli di relazione unari \(T\) e \(B\) e un simbolo di costante \(a\) interpretati come segue:
\(T(x) \leadsto\) “\(x\) è tedesco”;
\(B(x) \leadsto\) “\(x\) è biondo”;
\(a \leadsto\) Andrea.
\[\forall x (T(x) \to B(x)) \wedge \neg B(a) \to \neg T(a)\]
Esercizio Formalizzare in \(\mathbb{N}\) la seguente frase
Se ci sono numeri arbitrariamente grandi che soddisfano la proprietà \(P\), allora almeno uno di questi è un numero quadrato.
usando solo i simboli \(<\) e \(\cdot\) (interpretati nella maniera usuale) e il simbolo di relazione unario \(P\).
\[\forall x \exists y ( x < y \wedge P ( y ) ) \to \exists x ( P ( x ) \wedge \exists z(x = z \cdot z))\]
Alternativa più breve:
\[\forall x \exists y ( x < y \wedge P ( y ) ) \to \exists x P ( x \cdot x )\]
Esercizio Formalizzare in \(\mathbb{N}\) la frase
Ogni numero naturale sufficientemente grande è somma di quattro cubi.
usando solo i simboli \(<\), \(+\) e \(\cdot\) (interpretati nella maniera usuale).
\[\begin{gathered} \exists x \forall{ y} \bigl( x < y \to \exists z_{1} \exists z_{2} \exists z_{3} \exists z_{4} \bigr. \\ \bigl. \left ( y = z_{1} \cdot z_{1} \cdot z_{1} + z_{2} \cdot z_{2} \cdot z_{2} + z_{3} \cdot z_{3} \cdot z_{3} + z_{4} \cdot z_{4} \cdot z_{4} \right ) \bigr) \end{gathered}\]
Esercizio Formalizzare la frase
Nessun ladro è onesto, ma c’è un ladro gentiluomo che è onesto.
considerando come universo del discorso l’insieme di tutte le persone ed utilizzando il linguaggio del prim’ordine formato da tre simboli di relazione unari \(L\), \(O\) e \(G\) interpretati come segue:
\(L(x) \leadsto\) “\(x\) è un ladro”;
\(O(x) \leadsto\) “\(x\) è onesto”;
\(G(x) \leadsto\) “\(x\) è un gentiluomo”.
\[\neg \exists x \bigl (L(x) \wedge O(x) \bigr ) \mathbin{ \wedge } \exists x \bigl(L(x) \wedge G(x) \wedge O(x)\bigr)\]
Alternativa:
\[\forall x \bigl(L(x) \to \neg O(x)\bigr) \mathbin{ \wedge } \exists x \bigl(L(x) \wedge G(x) \wedge O(x) \bigr)\]
Esercizio Formalizzare la seguente frase
Se ci sono almeno tre elementi che soddisfano la proprietà \(P\), allora ci sono al più due elementi che soddisfano la proprietà \(Q\).
usando il linguaggio formato da due simboli di relazione unari \(P\) e \(Q\).
(Come universo del discorso si può prendere il dominio di qualunque \(L\)-struttura: per la sua forma, la frase è in questo caso indipendente dalla struttura scelta.)
\[\begin{gathered} \exists x \exists y \exists z \bigl (\mathord{ x \neq y} \mathbin{ \wedge } \mathord{x \neq z} \mathbin{ \wedge } \mathord{y \neq z} \mathbin{ \wedge } P (x) \mathbin{ \wedge } P ( y ) \mathbin{ \wedge } P ( z ) \bigr) \\ {} \to \neg \exists x \exists y \exists z \bigl ({x\neq y} \mathbin{ \wedge } {x\neq z} \mathbin{ \wedge } {y \neq z} \mathbin{ \wedge } Q ( x ) \mathbin{ \wedge } Q ( y ) \mathbin{ \wedge } Q ( z ) \bigr )\end{gathered}\]
Esercizio Formalizzare le frasi
C’è qualche impiegato che, pur lavorando bene, viene licenziato dal proprio capoufficio.
Il capoufficio di Ugo non licenzia alcun impiegato che lavori bene.
Qualunque impiegato che non lavori bene viene licenziato dal proprio capoufficio, a meno che si tratti di Ugo.
nel linguaggio formato da due predicati unari \(I\) e \(B\), un predicato binario \(L\), un simbolo di funzione unario \(c\) e un simbolo di costante \(u\), dove
\(I(x)\) se e solo se \(x\) è un impiegato;
\(B(x)\) se e solo se \(x\) lavora bene;
\(L ( x , y )\) se e solo se \(x\) licenzia \(y\);
\(c(x) =\) il capoufficio di \(x\);
\(u =\) Ugo.
Esercizio Formalizzare in \(\mathbb{N}\) la frase
Il più piccolo numero primo è pari.
usando i simboli \(<\), \(+\) (interpretati nella maniera usuale) e il predicato unario \(P\) per “essere un numero primo”.
\[\forall x \bigl(P(x) \wedge \forall y (P(y) \wedge y \neq x \to x < y) \to \exists z (x = z+z) \bigr)\]
Esercizio Formalizzare in \(\mathbb{N}\) la seguente frase
Preso un numero maggiore di \(1\) e il suo successore, tra i loro quadrati c’è sempre un numero primo.
usando i simboli \(<\), \(+\), \(\cdot\), \(1\) (interpretati nella maniera usuale) e il predicato unario \(P\) per “essere un numero primo”.
\[\forall x \forall y \bigl ( 1 < x \mathbin{ \wedge } y = x+1 \to \exists z ( P ( z ) \mathbin{ \wedge } x \cdot x < z < y \cdot y ) \bigr )\]
Alternativa più breve:
\[\forall x \bigl ( 1 < x \to \exists z ( P ( z ) \mathbin{ \wedge } x \cdot x < z < ( x + 1 ) \cdot ( x + 1 ) ) \bigr )\]
Esercizio Formalizzare la frase
Chi non studia e non svolge alcun esercizio non supera l’esame di logica.
in un linguaggio del prim’ordine con due simboli di relazione unari \(S\) e \(E\), due simboli di relazione binari \(F\) e \(P\), un simbolo di funzione unario \(f\) ed un simbolo di costante \(l\) interpretati come segue:
\(S(x) \leadsto\) “\(x\) studia”;
\(E(x) \leadsto\) “\(x\) è un esercizio”;
\(F(x,y) \leadsto\) “\(x\) svolge \(y\)”;
\(P(x,y) \leadsto\) “\(x\) supera \(y\)”;
\(f(x) \leadsto\) “l’esame della materia \(x\)”;
\(l \leadsto\) “logica”.
\[\forall{x} \bigl ( \neg S(x) \mathbin{ \wedge } \forall y (E(y) \to \neg F(x,y)) \to \neg P(x,f(l)) \bigr)\]